This invention relates to encryption apparatus in general and more particularly to an arithmetic circuit for computing larger unsigned integers to enable encryption of data for transmission over an insecure communications channel.
Cryptography is the science of transforming messages for the purpose of making the message unintelligible to all but the intended receiver. Essentially, the encryption of data employs such methods in various communication devices to establish communication security, authentication and digital signatures.
As one can ascertain, modern communication systems are being offered which increase the speed and accuracy of communications with lower costs. In any event, these systems present serious problems in regard to security. One way to prevent tampering with such systems and to protect the private information being transmitted requires such data such as credit information, security information and so on to be transformed by encryption techniques so that it becomes unintelligible and, therefore, useless to those who are not meant to have access.
Essentially, encryption is a special form of computation and such systems depend upon the difficulty of computation for their security. These systems affect transformation of 2 data which is so complicated that it becomes beyond the economical means of an unauthorized party to break the code or to reverse the process. Generally, the transformation used to encipher a message typically involves an algorithm and a key. While the general method used by a pair of correspondents may be public knowledge some or all of the key information must be kept secret. The process of transforming a message is to apply the enciphering algorithm to the message where the key is used as an auxiliary input to control the ciphering.
There have been many classical encryption techniques which have been extensively employed in the prior art and essentially consist of substitution ciphers. In any event, there are a class of encryption systems which are designated as public key cryptography systems. In such systems, the deciphering key is different from and not computable from the enciphering key. A person might create a matched pair of such keys and distribute copies of the enciphering key to all his associates while keeping the deciphering key secret. In this manner, the associates can send data to the creator which only he is capable of reading. Public key cryptography systems can also be used to provide digital signatures. Hence a user can create a signature for a message by enciphering it with a private key. Someone else can check the validity of the signature by checking that it deciphers to the message using the signer's public key.
A major type of cryptography system (RSA Cipher) enciphers a message B which is first coded into numeric form by, for example, setting values to each of the letters in the message and then using a public key (e,n) to obtain a ciphertext C as follows: EQU C=B.sup.E (Modulo M)
That is, C is the remainder of B.sup.E when divided by M. Here all quantities are large numbers which may be several hundred bits long and n is the product of two very large prime numbers p and q. The security of cipher rests mainly on the practical impossibility of factoring the letter n into its parts p and q. The deciphering operation is similar except that the exponent is different: EQU B=C.sup.D (Modulo M)
Since D depends on p and q, it is extremely difficult to compute D from e and M as it is to factor M. Depending on the number of bits in M, the process becomes extremely time consuming. As an example of the RSA method, the word "IT" can be encrypted as follows using the representation A=01, B=02, . . . Z=26. The number 0920 is indicative of the word "IT". Then with n=2773=47*59 and e=17, the cipher text is C=920.sup.17 (Modulo 2773)=948. Using p=47 and q=59, a value of d=157 can be derived from which the numbers can be calculated as 948.sup.157 (Modulo 2773)=920 which is "IT".
Modular arithmetic plays a large part in public key crytography systems because it turns smooth and continuous and continuously increasing or decreasing functions into discontinuous ones. This introduces a large factor of confusion making it extremely difficult to calculate the inverses. Hence if modularity is added, the value of a function jumps around in a haphazard way. Modular arithmetic is employed in many crytography systems to further disguise information which is already transformed by an enciphering function. Hence when modularity is added to such a system, the value of functions are thrown into complete disarray. As one will ascertain, while the encryption of data is relatively well known in regard to the techniques described above, there is a formidable problem regarding the implementation of such complicated functions. This is based on the tremendous size of the numbers used in regard to the bit length. Hence one requires huge storage capacity and extremely large times in computing encrypted values. As is known, the larger the numbers used, the more circuitry and more space and time are required to calculate functions of this kind. This places a severe limitations on hardware and software and hence such systems are associated with excessive cost. The main point regarding the complexity of such computations is the following. The encryption scheme should have the property that the code breaker's work increases much more rapidly with increasing N (the length of numbers) than does the work of an authorized sender or receiver. Assume the code breaking work is proportional to N.sup.N whereas the encrypting/decrypting work is proportional to N.sup.3. Then doubling N from 10 to 20 makes an authorized user's work eight times greater but the code breaker's work 40.sup.10 times greater. Translating work to cost might mean increasing the authorized person's costs from $10 to $80 but increasing the code breaker's cost from say a reasonable amount to an amount which would be more than the national budget of most countries.
For further information regarding such systems and the difficulty in computing and implementing the functions for encryption, reference is made to an article entitled "The Mathematics Of Public Key Cryptography" by Martin E. Hellman and published in SCIENTIFIC AMERICAN, August 1979, Vol. 241 #2, pages 146 to 157. This article is extremely informative in giving a detailed history of the development of cryptography and the problems inherent in such systems. The article also contains details concerning Modular arithmetic.
In regard to the problems experienced by the prior art, it is an object of this invention to provide an improved apparatus which is adapted to minimize the required circuit size to perform encryption calculations in a relatively fast time period and to implement an encryption algorithm which is extremely difficult to decipher without authorization.